// 选择固定的基准元素进行切分（此处选择第一个元素）
// 这种方法在处理有序数组时性能较差，时间复杂度为 O(n^2)

function quickSort(nums, left = 0, right = nums.length - 1) {
  if (left >= right) {
    return nums;
  }
  // 切分数组，返回基准元素的下标
  const pivotIndex = partition(nums, left, right);
  quickSort(nums, left, pivotIndex - 1);
  quickSort(nums, pivotIndex + 1, right);
  return nums;
}

function partition(nums, left, right) {
  // 选择区间里的第一个元素作为基准
  const pivot = nums[left];

  let j = left;
  
  // all in nums[left + 1 ... j] <= pivot
  // all in nums(j ... i) > pivot
  for (let i = left + 1; i <= right; i++) {
    if (nums[i] <= pivot) {
      j++;
      [nums[i], nums[j]] = [nums[j], nums[i]];
    }
  }
  [nums[left], nums[j]] = [nums[j], nums[left]];
  return j;
}

// 测试用例
const testCases = [
  [],
  [1],
  [5, 3, 8, 4, 2],
  [10, 9, 8, 7, 6, 5],
  [1, 2, 3, 4, 5],
  [3, 3, 3, 3],
  [5, -1, 0, 2, -3, 8]
];

for (const arr of testCases) {
  console.log(`原数组: [${arr}] => 排序后: [${quickSort(arr)}]`);
}